Difference-based filters compute the difference between an incoming sample and sample(s) stored in the filter to determine a new output value. Such filters are designed to operate on linear data. However, difference-based filters, including median and low-pass filters, do not operate correctly on ‘circular’ data, such as longitude, heading, or track angle, until the data has been linearized or normalized. For example, a typical filter will see heading angles of +179 degrees and −179 degrees, which are only two degrees apart, as being 358 degrees apart, and an incorrect filter output is generated. A typical solution in the art is to first to re-scale the input signal into a fixed-point binary number using the natural word width of the hardware, which must be known beforehand. Next the re-scaled number is filtered using fixed-point arithmetic, fixed-point scale factors, and overflow compensation. Finally the number is optionally re-scaled back to engineering units. For systems that use floating point hardware, this solution requires two extra multiply operations, overflow tests, and custom development of fixed-point filter algorithms for the specific set of signals. The typical algorithms may also truncate the range or resolution of the signal in some cases.
One known difference-based filter is a median filter. Simply stated, a median filter picks the middle value from among an odd number of candidates. When the data lie on a line, the picking process is a simple concept.
As described more generally in U.S. Pat. No. 5,900,006, which is incorporated by reference herein in its entirety, a median filter is a non-linear filter which outputs data of a medium magnitude as a median value among a predetermined number of data.
FIG. 1 shows a block diagram of a conventional median filter. A series of input data is continuously supplied to an input port and each input datum passes through a cascade of N delay elements V[1] to V[N], one input datum to one element at a time, each input datum being delayed at each delay element, N being an odd positive integer greater than 1. When a new input datum I[0] is applied to the input port, each of N preceding input data I[1], to I[N−1] will be available as an output from each corresponding delay element at a time. A set of these input data I[0] to I[N−1] from the input port and the N delay elements V[1] to V[N] is supplied to a sorter 10 simultaneously, wherein the N input datum provided to the sorter 10 at a time represents the window size of a predetermined magnitude. The sorter 10 is necessary to rearrange the set of these input data I[0] to I[N−1] according to the order of their magnitude. Subsequently, a median value is selected and provided to an output port, wherein the median value represents an input data value corresponding to the median data in the newly arranged set.
When another new input datum I[A] is applied to the input port, each input datum held at each corresponding delay element is transferred to each corresponding next delay element in the series of the delay elements, i.e., I[N−1] held at V[N−1 ] being transferred to V[N], replacing I[N] previously held at V[N] and so on, thereby forming a new set of input data I[A], I[0], . . . I[N−2] including the new input data I[A]. The new set of input data is fed to the sorter 10 and then rearranged once again according to the order of their magnitude, independent of the order of the data sorted in a former sorting procedure, to repeat the process of selecting a median value for the new set of input data. The time to sort for a median value generally increases as the size of the window increases. Adding lag, or phase delay, to the output signal of the conventional median filtering procedure as described above is problematic for real-time control systems because of the reduced system efficiencies that result.
Consequently, only with difficulty does a conventional median filter accommodate a large or variable size of window in response to a high level of variable impulse noises in the input data being filtered.
FIG. 2 illustrates an existing fifth order median filter as described by U.S. Pat. No. 5,968,111, which is incorporated by reference herein in its entirety. In FIG. 2, median cells 11–15 store five recently input data values. The five data values stored in the median cells 11–15 are sorted in a descending order from the data value stored in the leftmost median cell 11. The datum value DATA_IN input to the median filter of FIG. 2 is individually compared with the stored data values in the median cells 11–15. Then, according to the comparison result, the input datum is stored in one of the median cells 11–15 in a manner that a descending order is maintained. At the same time, the datum which was firstly input to the median filter of FIG. 2 is deleted. In this manner, the data stored in the respective median cells 11–15 always maintain a descending order. As a result, the median filter can output a middle value stored in the median cell 13 which is positioned in the middle of the median cells 11–15, as a median value OUT.
FIG. 3 illustrates one embodiment of another known difference-based filter, the first-order low-pass filter 20. Derivatives of the low-pass filter are the high-pass and band-pass filters. Many different algorithms are known for implementing low-pass filters, all having a general characteristic of determining the difference between the input and output signals, and applying a portion of the difference to the output signal through a variety of feedback and scaling mechanisms.
In FIG. 3, the previous filter stored value G(M−1) is subtracted from the filter input FI. The difference is multiplied by a gain factor C and added to the previous filter stored value to create a new filter stored value G(M). In the example implementation, the previous and the new filter output values are averaged to create the filter output value FO. The first-order low-pass filter in FIG. 3 includes a roll-over check for circular data on the difference signal resulting from subtracting previous filter stored value G(M−1) from the filter input FI and on the newly created filter stored value G(M). A roll-over check for circular data is also performed on the filter output value FO.
The high-pass is generated by simply subtracting low-pass filter output from filter input according to: FO=FI−LPF(FI).
The bandpass filter is generated in similar known fashion.
The problem of applying circular data to a difference-based filter, such as the low-pass filter or its derivatives, is evident when the input signal value crosses over the breakpoint, for example, when the input signal value rolls from 359 degrees to zero degrees, or +π radians to −π radians. Without normalization a large difference signal (approximately 360 degrees or 2π radians) is input to the filter, which causes a large step in the output when a very small step in the opposite direction is what is desired.
FIG. 4 shows the definition of a domain of data expressed as a line segment AB. Five data values are shown as x[0], x[1], x[2], x[3], x[4]. The numerical value of a point is the signed distance (difference in coordinates) between that point and endpoint A. The median filter of FIG. 2 is appropriate to use on these data because the domain is linear and the filter only handles data for which the linear sort order is clearly defined.
When the data lie on a circle, however, picking the median value becomes conceptually more difficult. The common sense approach is to first assume that the “distance” between two co-circular points is the lesser of the two angles separating them, never more than 180 degrees; linearize the data by choosing the angular range that includes all the samples corresponding to the largest distance that can be computed from the samples; and pick the middle sample in this angular range. For the special case of multiple co-circular data samples separated by equal angles, special rules must be applied. Such special cases include the exemplary cases of three samples separated by 120 degree and five separated by 72 degree, et cetera.
FIG. 5 illustrates a definition of a domain of data expressed as angles on a circle C, in which angles “0” and “2π” correspond to the same point on the circle C. The above incorporated U.S. Pat. No. 5,968,111 describes one example of a conventional median filter applied to determine the median value among the data points according to the definition domain illustrated in FIG. 5, wherein the multiple co-circular data points on the circle C correspond to angles having a circularly corresponding relationship as angle increases. In the case when the following data points are input:R[0]=theta[1], R[1]=theta[2], R[2]=theta[3], R[3]=2πtheta[2],where:0<theta[1]<theta[2]<theta[3]<π/2,because the existing median filter compares only magnitudes of data, R[2] is output as a median value, which is not a desired median value. The desired median value is R[0], as shown in FIG. 5. Thus, the existing median filter does not provide an appropriate median value with respect to data expressed as angles without pre-normalization.
U.S. Pat. No. 5,968,111 describes one method for implementing a circular median filter for determining the median value among multiple co-circular data points. According to the method described by U.S. Pat. No. 5,968,111, range normalization starts with distance computation between neighboring pairs of cells, and distance is always positive. The input cells are first sorted by magnitude. The method of U.S. Pat. No. 5,968,111 requires N additional storage locations, N−1 distance calculations, and on the order of N^2 comparison operations. Thus, the circular median filter algorithm as exemplified by U.S. Pat. No. 5,968,111 is computation intensive and memory intensive, especially for larger data sets.